Masala #0741

Uchburchakli sonlar teng tomonli uchburchakda joylashtirilgan jismlar sonidir (shu tariqa uchburchakli sonlar figurali sonlar turiga kiradi). N-chi uchburchakli son - bu yon tomonda n ta nuqta bo'lgan uchburchak tartibidagi nuqtalar soni va 1 dan n gacha bo'lgan n ta natural sonning yig'indisiga teng miqdorda nuqtadan iboratdir. Uchburchakli sonlar 1-tartibdan boshlanadi va dastlabki elementlari quyidagilardir:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210, 231, 253, 276, 300, 325, 351, 378, 406, 435, 465, 496, 528, 561, 595, 630, 666...

Quyida 1 dan 6 gacha tartibdagi uchburchakli sonlar ifodalangan:

Sizning vazifangiz berilgan N sonini aynan 3 ta uchburchakli sonlar yig’indisi shaklida yozish mumkin yoki yo’qligini aniqlashdan iborat.

Kirish faylining dastlabki satrida bitta butun son, $T(1 \le T \le 10^5)$ testlar soni kiritiladi.

Keyingi $T$ ta satrda har bir test uchun bitta butun son $N (1 \le N \le 10^{18})$ soni kiritiladi.

Chiqish faylining yagona satrida N ta butun son (orasida hech qanday ajratgichlarsiz), har bir test uchun agar N soni yuqoridagi shartni qanoatlantirsa 1 aks holda 0 sonini chop eting.